package com.googlecode.gaal.suffix.algorithm.impl;

import java.util.Stack;

import com.googlecode.gaal.suffix.algorithm.api.ChildTableBuilder;

public class KimChildTableBuilder implements ChildTableBuilder {

    @Override
    public int[] buildChildTable(int[] lcpTable) {

        int n = lcpTable.length - 1;
        int[] cldtab = new int[n + 1];
        Stack<Integer> stack = new Stack<Integer>();

        // The CHILD procedure
        stack.push(0);
        int lastIndex = -1;
        for (int i = 1; i <= n; i++) {
            while (lcpTable[i] < lcpTable[stack.peek()]) {

                lastIndex = stack.pop();
                if (lcpTable[i] < lcpTable[stack.peek()] && lcpTable[stack.peek()] != lcpTable[lastIndex]) {
                    cldtab[stack.peek()] = lastIndex;
                }
            }
            if (lastIndex != -1) {
                cldtab[i - 1] = lastIndex;
                lastIndex = -1;
            }
            stack.push(i);
        }

        // Kim et al say that lcptab should be padded with a sentinel
        // value: -2. The following has the same effect and avoids
        // having to modify lcptab.
        lastIndex = stack.pop();
        while (!stack.isEmpty()) {
            if (lcpTable[stack.peek()] != lcpTable[lastIndex]) {
                cldtab[stack.peek()] = lastIndex;
            }
            lastIndex = stack.pop();
        }
        cldtab[n] = lastIndex;

        // The NEXT procedure
        stack.push(0);
        for (int i = 1; i <= n; i++) {
            while (lcpTable[i] < lcpTable[stack.peek()]) {
                stack.pop();
            }
            if (lcpTable[i] == lcpTable[stack.peek()]) {
                lastIndex = stack.pop();
                cldtab[lastIndex] = i;
            }
            stack.push(i);
        }
        return cldtab;
    }

}
